∃ a Problem with the PRNG in Java

(found while reading the current XKCD)

Java’s “random” number generator has some surprisingly simple patterns in it. Nearly all random number generators on computers are pseudo-random, meaning that they only seem random-ish and are not truly random (with some notable but impractical exceptions). This happens because computers themselves are deterministic and therefore inherently non-random. Most pseudo-random number generators these days use the previous “random” value as an input to create the new value, which will be used to create the next one after that (which is why plots like these are often used to evaluate the effectiveness of a PRNG: by plotting the current value with the previous one, you can see how much the values get scattered around the range of outputs). As an aside, I should note that plotting the same thing in 3-D (with the current value, the previous value, and the value before that as the 3 coordinates) can reveal other problems, such as the problems in Randu, an early PRNG. Anyway, because most PRNGs use their previous value to compute the next one, they will cycle after they get the same value twice. A good PRNG that generates n-bit numbers shouldn’t cycle until it has generated 2n of them. Java’s implementation appears to be much worse than this, which is disappointing. Come on, guys, you can do better! The cryptographically secure hash is my favourite, and I’m currently trying to prove that NC≠P using a variation of this. If it’s any consolation to Sun (the creators of Java), Matlab has similar problems.

Leave a Reply

4 Comments

  1. janna says:

    Isn’t Matlab written in Java and therefore probably just using Java’s PRNG? I know at least the gui is done in Java…

    • Alan says:

      You’re right that the GUI is written in Java. The underlying mathematical functions (such as the FFT and the matrix multiplication) are written in machine code to make them fast. I don’t know how its PRNG is implemented, but I wouldn’t be surprised if it had its own version (Matlab has a bunch of reinvented wheels inside it).

  2. kitty_tape says:

    You mean yesterday’s xkcd isn’t the ideal random number generator? =)

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>